package tree.rysz;

/**
 * sample Kruskal.java Description:
 * kruskal算法的思想是找最小边，且每次找到的边不会和以找出来的边形成环路，利用一个一维数组group存放当前顶点所在连通图标示（每条最小边，属于一个连通图），直到顶点都找完 
 * 1.0 YESUN Jul 18,
 * 2013 8:48:28 AM Create. ChangeLog:
 */
public class Kruskal2 {
    


    /**
     * Description:
     * 
     * @param args
     *            1.0 YESUN Jul 18, 2013 8:47:10 AM Create. ChangeLog:
     */
    public static void main(String[] args) {
        double[][] map = new double[][]{{1,0.053626866,0.058155746,0.096684177,0.014720232,0.143771834,0.370189875,0.459644309,0.364978852,0.449248707,0.490003812,0.455165287,0.403534654},
        	{0.053626866,1,0.022639675,0.035698448,0.023823814,0.079699893,0.305948251,0.545317545,0.460063773,0.49343927,0.370705789,0.350918044,0.298698281 },
        	{0.058155746,0.022639675,1,0.05669572,0.019129818,0.137537063,0.354151603,0.657142857,0.534354362,0.619221963,0.49922509,0.469365943,0.397020804  },
        	{0.096684177,0.035698448,0.035698448,1,0.080125967,0.021337179,0.225622352,0.507448971,0.411068064,0.468739546,0.362335087,0.324313752,0.276489189},
        	{0.014720232,0.023823814,0.023823814,0.019129818,1,0.146686436,0.374509871,0.555975779,0.452773142,0.527188156,0.482846147,0.455713023,0.394128801},
        	{0.143771834,0.079699893,0.079699893,0.137537063,0.021337179,1,0.004402597,0.211144056,0.148892017,0.371935187,0.294466317,0.259073262,0.2339081  },
        	{0.370189875,0.305948251,0.305948251,0.354151603,0.225622352,0.374509871,1,0.231964663,0.160354911,0.399279869,0.325183838,0.283065609,0.255883576},
        	{0.459644309,0.545317545,0.545317545,0.657142857,0.507448971,0.555975779,0.211144056,1,0.023923937,0.210582118,0.415762605,0.386454371,0.415863904},
        	{0.364978852,0.460063773,0.460063773,0.534354362,0.411068064,0.452773142,0.148892017,0.160354911,1,0.243199131,0.440691623,0.395489213,0.400621587},
        	{0.449248707,0.49343927,0.49343927,0.619221963,0.468739546,0.527188156,0.371935187,0.399279869,0.210582118,1,0.338709911,0.319492983,0.34921525   },
        	{0.490003812,0.370705789,0.370705789,0.49922509,0.362335087,0.482846147,0.294466317,0.325183838,0.415762605,0.440691623,1,0.205280586,0.217340026 },
        	{0.455165287,0.350918044,0.350918044,0.469365943,0.324313752,0.455713023,0.259073262,0.283065609,0.386454371,0.395489213,0.319492983,1,0.207127156},
        	{0.403534654,0.298698281,0.298698281,0.397020804,0.276489189,0.394128801,0.2339081,0.255883576,0.415863904,0.400621587,0.34921525,0.217340026,1   }
        };
        kruskal(map);
    }
    
    static int MAX = Integer.MAX_VALUE;
    
    /**
     * Description: by yesun
     * @param arcs
     * 1.0 YESUN Jul 18, 2013 1:42:42 PM Create.
     * ChangeLog:
     */
    public static void kruskal(double[][] arcs) {
        //顶点个数
        int num = arcs.length;
        //存放对应顶点所在连通图标识
        int[] group = new int[num];
        
        double sum = 0;
        int n1 = 0, n2 = 0;
        boolean finished = false;
        int groupNum = 1;
        
        while(!finished) {
            double min = Integer.MAX_VALUE;
            //找出所有边中最小值
            for(int i = 0; i < num; i++) {
                for(int j = i; j < num; j++) {
                	//System.out.println(i+"~"+j+":"+min);
                    if(arcs[i][j] > 0 && arcs[i][j] < min){
                        //如果group相同，则表示处理过，不相同或都为0都表示没处理过
                        if (group[i] != group[j] || (group[i] == 0 && group[j] == 0)) {
                            min = arcs[i][j];
                            n1 = i;
                            n2 = j;
                        }                                            
                    }
                }
            }
            
            if(min == Integer.MAX_VALUE){
                continue;
            }
            
            System.out.println(n1 + " ---> " + n2 + " " + min);
            sum += min;
            
            //找到了最小值，设置连通标记
            if(group[n1] == 0 && group[n2] == 0){
                group[n1] = groupNum;
                group[n2] = groupNum;
                groupNum++;
            }
            else if(group[n1] > 0 && group[n2] > 0) {
                int tmp = group[n2];
                for(int m = 0; m < group.length; m++){
                    if(group[m] == tmp){
                        group[m] = group[n1];
                    }
                }
            }
            else{
                if(group[n1] == 0){
                    group[n1] = group[n2];
                }
                else{
                    group[n2] = group[n1];
                }
            }
            
            for(int i = 0; i < group.length; i++) {
                if(group[i] != group[0]){
                    finished = false;
                    break;
                }
                else{
                    finished = true;
                }
            }
            
            if(finished) {
                break;
            }
        }
        
        System.out.println(" sum:"+sum);
        
    }

}